/*
https://leetcode-cn.com/problems/find-eventual-safe-states/solution/zhao-dao-zui-zhong-de-an-quan-zhuang-tai-yzfz/
 */
import java.util.*;

public class Solution802 {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<List<Integer>> rg=new ArrayList<>();
        for (int i=0;i<graph.length;i++){
            rg.add(new ArrayList<>());
        }
        int[] d=new int[graph.length];
        for (int i=0;i<graph.length;i++) {
            for (int j=0;j<graph[i].length;j++) {
                rg.get(graph[i][j]).add(i);
                d[i]++;
            }
        }
        Queue<Integer> queue=new LinkedList<>();
        for (int i=0;i<graph.length;i++){
            if (d[i]==0){
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int t=queue.poll();
            for (Integer i : rg.get(t)) {
                d[i]--;
                if (d[i]==0){
                    queue.offer(i);
                }
            }
        }
        List<Integer> ans=new ArrayList<>();
        for (int i=0;i<graph.length;i++){
            if (d[i]==0){
                ans.add(i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution802().eventualSafeNodes(new int[][]{{1,2},{2,3},{5},{0},{5},{},{}}));
    }
}
